/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package org.sss.tools;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;


/**
 * Class responsible for finding a list of shops including products in these stores.
 * @author Przemyslaw Wojtysiak
 */
public class SearchProductAlgorithm {
    
    /**
     * The list of nodes that contain one store. The initial list of nodes.
     */
    private List<Node> allNodes;
    /**
     * Maximum number of shops, the user has to go shopping.
     */
    private int maxDepth = 4;
    /**
     * All possible combinations of the shops, 
     * to which the user can go in a given time and for a list of products.
     */
    private List<Node> possiblePaths;
    private List<Node> possiblePaths2;
    /**
     * List of stores that contain at least one specified by the user of the product.
     */
    private List<Shop> shops;
    /**
     * Starting node - contains the coordinates of the user.
     */
    private Node startNode;
    /**
     * List of all possible ProductShop
     */
    private List<ProductShop> productShops;
    /**
     * Type of transport, which moves the user.
     * 0 - walk
     * 1 - bike
     * 2 - car
     */
    private int transport;
    /**
     * The maximum time in which to be searched for stores with products with an optimal price.
     */
    private Double time;
    
    /**
     * SearchProductAlgorithm class constructor.
     * @param transport
     * @param time 
     */
    public SearchProductAlgorithm(int transport, Double time){
        allNodes = new ArrayList<Node>();
        possiblePaths = new ArrayList<Node>();
        possiblePaths2 = new ArrayList<Node>();
        shops = new ArrayList<Shop>();
        this.transport = transport;
        this.time = time;
    }
    
    /**
     * Depth-first search algorithm.
     * @param node
     */
    public void DFS(Node node) {
        //Calculate the distance between the previous and the current shop.
        node.setDistance(countDistance(node.getParent().getShop().getX(), node.getParent().getShop().getY(), 
                    node.getShop().getX(), node.getShop().getY()));
        
        node.setTime(changeDistanceToTime(node.getDistance()) + node.getParent().getTime() + 10.0);
        
        node.setDepth(node.getParent().getDepth() + 1);
        
        //set of all possible unvisited nodes.
        List<Node> nextNodes = new ArrayList<Node>(node.getParent().getNodeToVisit());
        for (int i = 0; i < nextNodes.size(); i++) {
            if (nextNodes.get(i).getShop().getIdshop() == node.getShop().getIdshop()) {
                nextNodes.remove(i);
                break;
            }
        }
        node.setNodeToVisit(nextNodes);
        
        //addition products which were not yet in stores earlier and are in the current store.
        List<ProductShop> products = new ArrayList<ProductShop>(node.getParent().getActualProducts());
        boolean isNewProductInThisShop = false; 
        Double timeTmp = 0.0;
        boolean isProductInActualList = false;
        for(int i = 0; i < node.getProductsInShop().size(); i++) {
            isProductInActualList = false;
            for (int j = 0; j < products.size(); j++) {
                if (node.getProductsInShop().get(i).getName().equals(products.get(j).getProduct().getName())) {
                    isProductInActualList = true;
                    break;
                }
            }
            if (isProductInActualList == false) {
                products.add(new ProductShop(node.getShop(), node.getProductsInShop().get(i)));
                timeTmp += 5.0;
                isNewProductInThisShop = true;
            }
        }
        

        //if in the current store are cheaper products that are swapped with those 
        //that were on the current list of products.
        for (Product product : node.getProductsInShop()) {
            for (int i = 0; i < products.size(); i++) {
                if (product.getName().equals(products.get(i).getProduct().getName())) {
                    if (product.getPrice() < products.get(i).getProduct().getPrice()) {
                        products.remove(i);
                        products.add(new ProductShop(node.getShop(), product));
                        isNewProductInThisShop = true;
                        break;
                    }
                }
            }
        }
        //if you have added at least one new product 
        //to the list of current products from the current store - continue the algorithm.
        if (isNewProductInThisShop == true) {
            node.setActualProducts(products);
            node.setTime(node.getTime() + timeTmp);
            
            //calculate the current price for the products in the current shopping list.
            Double totalPriceForProduct = 0.0;
            for (ProductShop productShop : products) {
                totalPriceForProduct += productShop.getProduct().getPrice();
            }
            node.setActualPriceForProducts(totalPriceForProduct);
            node.setTotalPrice(totalPriceForProduct);
            
            //setting the number of products contained in the current shopping list.
            node.setActualNumberOfProducts(products.size());
            
            //if the time needed to go shopping in the current node 
            //is less than or equal to the maximum time that user gave 
            //- continue the algorithm.
            if (node.getTime() <= this.time) {
                //add a node to the possible nodes that can contain an optimal price.
                possiblePaths.add(node);
                
                //if the current store was less than the "maxDepth" visited the shop - continue the algorithm.
                if (node.getDepth() < maxDepth) {
                    for (int i = 0; i < node.getNodeToVisit().size(); i++) {
                        Node child = new Node(node.getNodeToVisit().get(i));
                        //setting the current Store as the parent for the next neighboring node.
                        child.setParent(node);
                        
                        //execution DFS algorithm for neighboring node
                        DFS(child);
                    }
                }
            }
        }
    }
    
    /**
     * The method of converting given distance in time.
     * walk - every 1000 meters in 16 minutes
     * bike - every 1000 meters in 6 minutes
     * car - every 1000 meters in 3 minutes
     * @param distance
     * @return result as time
     */
    public double changeDistanceToTime(double distance) {
        double result = 0.0;
        if (transport == 0) {
            result = (distance * 16.0) / 1000.0;
        }
        else if (transport == 1) {
            result = (distance * 6.0) / 1000.0;
        }
        else {
            result = (distance * 3.0) / 1000.0;
        }
        return result;
    }
    
    /**
     * The initialize method. Start execution of the algorithm.
     * @param productsShops
     * @param x
     * @param y 
     */
    public void init(List<ProductShop> productsShops, Double x, Double y) {
        productShops = productsShops;
        createShops(productsShops);
        createNodes(x,y);
        
        for (int i = 0; i < startNode.getNodeToVisit().size(); i++) {
            Node node = new Node(startNode.getNodeToVisit().get(i));
            node.setParent(startNode);
            for (int j = 0; j < possiblePaths.size(); j++) {
                Node node3 = new Node(possiblePaths.get(j));
                
                possiblePaths2.add(node3);
            }
            possiblePaths.clear();
           
            DFS(node);
        }
        for (int j = 0; j < possiblePaths.size(); j++) {
                Node node3 = new Node(possiblePaths.get(j));
                possiblePaths2.add(node3);
        } 
    }

    /**
     * A method that creates a list of stores that contain at least one product. 
     * This is to speed up the algorithm so as not to search 
     * for products in stores that do not contain any.
     * @param productsShops 
     */
    private void createShops(List<ProductShop> productsShops) {
        shops.add(productsShops.get(0).getShop());
        boolean tmp = false;
        for (int i = 0; i < productsShops.size(); i++) {
            tmp = false;
            for (int j = 0; j < shops.size(); j++) {
                if (shops.get(j).getIdshop() == productsShops.get(i).getShop().getIdshop()) {
                    tmp = true;
                    break;
                }
            }
            if (tmp == false) {
                shops.add(productsShops.get(i).getShop());
            }
        }
    }

    /**
     * Creating nodes, containing a shop and creating start node.
     * @param x
     * @param y 
     */
    private void createNodes(Double x, Double y) {
        for (Shop shop : shops) {
            Node node = new Node();
            node.setActualNumberOfProducts(0);
            node.setActualPriceForProducts(0.0);
            node.setDepth(0);
            node.setDistance(0.0);
            node.setShop(shop);
            node.setTotalPrice(0.0);
            List<Product> productsInShop = new ArrayList<Product>();
            for (ProductShop productShop : productShops) {
                if (productShop.getShop().getIdshop() == shop.getIdshop()) {
                    productsInShop.add(productShop.getProduct());
                } 
            }
            node.setProductsInShop(productsInShop);
            node.setTime(0.0);
            allNodes.add(node);
        }
        Shop shop = new Shop();
        shop.setIdshop(0);
        shop.setName("MyPosition");
        shop.setX(x);
        shop.setY(y);
        
        startNode = new Node(0.0, shop, 0, 0, 0.0, 0.0, 0.0);
        startNode.setNodeToVisit(allNodes);
    }
    
    /**
     * Auxiliary method to calculate the distance in meters between two points.
     * @param x1
     * @param y1
     * @param x2
     * @param y2
     * @return 
     */
    public double countDistance(double x1, double y1, double x2, double y2) {
        double theta = y1 - y2;
        double dist = Math.sin(deg2rad(x1)) * Math.sin(deg2rad(x2)) + Math.cos(deg2rad(x1)) * Math.cos(deg2rad(x2)) * Math.cos(deg2rad(theta));
        dist = Math.acos(dist);
        dist = rad2deg(dist);
        dist = dist * 60 * 1.1515;
        dist = dist * 1.609344;
        return dist * 1000;
}
    
    /**
     * Auxiliary method to calculate the distance
     * @param deg
     * @return 
     */
    private double deg2rad(double deg) {
        return (deg * Math.PI / 180.0);
    }

    /**
     * Auxiliary method to calculate the distance
     * @param rad
     * @return 
     */
    private double rad2deg(double rad) {
        return (rad * 180.0 / Math.PI);
    }

    /**
     * The method returns a list ProductShop for node with 
     * the most sophisticated products and optimal price.
     * @return list of ProductShop
     */
    public List<ProductShop> getShops() {
        
        System.out.println("------------------The best result-------------------------------------");
        if (!possiblePaths2.isEmpty()) {
        Collections.sort(possiblePaths2, new SortNodes());
            Node node = new Node(possiblePaths2.get(0));
            System.out.println("------------------");
            System.out.println("Actual price: " + node.getActualPriceForProducts());
            System.out.println("Total price: " + node.getTotalPrice());
            System.out.println("Total time: " + node.getTime().toString());
            System.out.println("Number of products: " + node.getActualNumberOfProducts());
            for (ProductShop ps : node.getActualProducts()) {
                System.out.println("Product name: " + ps.getProduct().getName() + 
                        " Price: "+ps.getProduct().getPrice() + " Shop: " + ps.getShop().getName());
            }
        }
        if (!possiblePaths2.isEmpty()) {
            Node node3 = new Node(possiblePaths2.get(0));
            return node3.getActualProducts();
        }
        List<ProductShop> ps = new ArrayList<ProductShop>();
        return ps;
    }
}

/**
 * An auxiliary class is responsible for sorting a list of all possible combinations of nodes.
 * @author Przemyslaw Wojtysiak
 */
class SortNodes implements Comparator<Node>{

    /**
     * The method responsible for sorting a list of all possible combinations of nodes.
     * @param o1
     * @param o2
     * @return 
     */
    @Override
    public int compare(Node o1, Node o2) {
        if (o1.getActualNumberOfProducts() > o2.getActualNumberOfProducts()) {
            return -1;
        }
        if (o1.getActualNumberOfProducts() == o2.getActualNumberOfProducts()) {
            if (o1.getTotalPrice() > o2.getTotalPrice()) {
                return 1;
            }
            else if (o1.getTotalPrice() < o2.getTotalPrice()) {
                return -1;
            }
            else {
                if (o1.getTime().equals(o2.getTime())) {
                    Integer tmp1 = new Integer(o1.getDepth());
                    Integer tmp2 = new Integer(o2.getDepth());
                    return tmp1.compareTo(tmp2);
                }
                else
                {
                    return o1.getTime().compareTo(o2.getTime());
                }
            }
        }
        return 1;
    }
}
